`
https://leetcode.cn/problems/distinct-subsequences/
`

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
  // 存放已计算的结果，避免重复计算
  const memo = Array.from({ length: s.length }, () => new Array(t.length).fill(-1))

  // 定义：s[i..] 的子序列中 t[j..] 出现的次数为 dp(i, j)
  function dp(i, j) {
    // t 匹配完了，说明有一个结果
    if (j === t.length) {
      return 1
    }

    // s 剩余的长度不够给 t 全部匹配完，说明不可能有结果
    if (s.length - i < t.length - j) {
      return 0
    }

    // 如果已经计算过，直接从缓存里拿结果
    if (memo[i][j] !== -1) {
      return memo[i][j]
    }

    let res = 0
    // 状态转移方程：dp(s, i, t, j) = SUM( dp(s, k + 1, t, j + 1) where k >= i and s[k] == t[j] )
    for (let k = i; k < s.length; k++) {
      // 如果字符能匹配，进入下一层匹配下一个字符
      if (s[k] === t[j]) {
        res += dp(k + 1, j + 1)
      }
      // 如果字符不匹配，继续在 s 中寻找下一个字符
    }

    // 记录计算结果
    memo[i][j] = res
    // 返回结果
    return res
  }

  return dp(0, 0)
};